This paper describes a class of strategies for reducing persistent contrail formation in the United States airspace. The primary objective is to minimize potential contrail formation regions by altering the aircraft's cruising altitude in a fuel-efficient way. The results show that the contrail formations can be reduced significantly without extra fuel consumption and without adversely affecting congestion in the airspace. The contrail formations can be further reduced by using extra fuel. For the day tested, the maximal reduction strategy has a 53% contrail reduction rate. The most fuel-efficient strategy has an 8% reduction rate with 2.86% less fuel-burnt compared to the maximal reduction strategy. Using a cost function which penalizes extra fuel consumed while maximizing the amount of contrail reduction provides a flexible way to trade off between contrail reduction and fuel consumption. It can achieve a 35% contrail reduction rate with only 0.23% extra fuel consumption. The proposed fuel-efficient contrail reduction strategy provides a solution to reduce aviation-induced environmental impact on a daily basis.